As modern data communication systems transmit data at increasingly higher rates, the reliability of the data becomes more difficult to guarantee. Digital communications engineers know that a channel code can be used to improve the reliability of transmitted data. The fundamental idea behind channel coding is to introduce controlled redundancy into the data to be transmitted. This controlled redundancy allows for detection of, and subsequent recovery of some transmission errors. Channel coding is also often referred to as forward error control (FEC) or error control coding (ECC).
Two main methods of channel coding exist: block coding and trellis coding. (Only binary codes will be addressed to simplify the discussion.) Block coding calls for independent blocks of binary date to be encoded into independent codewords, which are themselves blocks of binary symbols (also known as vectors). Therefore, a block encoder input bit stream is sectioned into independent blocks of the same length that the encoder maps onto independent codewords, often also of the same length.
The ratio of the codeword length to the data block length is the “code rate. ” As an example, the following table describes a simple rate-⅔ block code rate encoder which encodes blocks of two user bits (d0d1) into codewords having a lenght of three bits (c0c1c2):
TABLE 1A Simple Block Code and Encoderd0d1c0c1c200000010111011011101
For a block code, the code is the collection of codewords, {000,001,110,101} in the example, while the encoder specifies the mapping of pairs (d0d1) to triplets (c0c1c2). Therefore, by rearranging the rows of Table 1 under “d0d1,” the encoder is changed, but not the code. Controlled redundancy is introduced into the data pair by a simple encoding rule:c0=d0c1=d0⊕d1c2=d1where ⊕ denotes a binary exclusive OR (XOR) operation. The redundancy gives the code the property that every codeword has even parity, which allows detection (but not correction in this relatively trivial example) of single errors in a codeword.
It is customary when discussing channel coding, to refer to the “coding gain” of a particular code. “Coding gain” can be thought of as the amount by which the transmitter power may be reduced when using the code, relative to that required by the same system without use of the code. In both cases, the system operates at the same bit error rate (BER). Thus coding may be used either to decrease the BER with the same transmitter power or to decrease transmitter power without decreasing the BER. It can be shown that an optimal decoder for the simple block code in Table 1 achieves a coding gain of 1.2 dB in an additive white Gaussian noise (AWGN) channel using 2-PAM modulation at moderate signal-to-noise ratios (SNR).
Another operation performed in a communication system is modulation, which is the selection of distinct electrical or optical waveforms to represent the information to be transmitted. These waveforms are suitable for actual energy transmission over the physical channel. In data communication systems, it is typical to provide only a finite number of waveforms from which the modulator may choose at a given instant. These waveforms can differ in one or more characteristics such as amplitude, phase or frequency.
One particular type of modulation, known as M-Pulse Amplitude Modulation (M-PAM), calls for a modulator to select and transmit one of M waveforms in response to log2M bits. The waveforms differ from one another only in amplitude. It is customary, in discussing M-PAM modulation, to refer only to the different waveform amplitudes using the set of integers {Am} withAm=2m−1−M, m=1, 2, . . . , M.{Am} is referred to as the symbol alphabet. The simplest case occurs for M=2 for which the symbol alphabet is {−1,+1}. For M=4, the corresponding symbol alphabet is {−3,−1,+1,+3}.
In many data communications systems, the operations of channel coding and modulation are performed independently, with the modulation operation performed subsequent to channel coding. As an example of how this process works, consider the transmission of the information sequence {1,0,1,1} (groups of binary symbols are underlined to emphasize block boundaries) by first error control encoding using the simple code above and 2-PAM modulation. The output of the channel encoder is the sequence {1,1,0,1,0,1}. This bit sequence is then mapped by the modulator into the channel symbol sequence {+1,+1,−1,+1,−1,+1} using the modulator mapping function:
Bit ValueChannel Symbol0−11+1
Trellis coding differs from block coding in two key ways. First, the encoders have memory, which allows the encoder output in response to a particular input block to change with time. Thus, no fixed encoder mapping needs to exist between input bit blocks and output code words. Second, the modulation operation is usually an integral part of the encoder and thus contributes to the effectiveness of the code. One of the earliest references in the technical literature to this combined channel coding modulation is Massey (see, Massey, “Coding and Modulation in Digital Communications,” Proc. 1974 Int. Zürich Seminar on Digital Comm., Zürich, Switzerland, pp. E2 (1)-(4), March 1974, incorporated herein by reference)
Ungerboeck (see, Ungerboeck, “Channel Coding with Multilevel Phase Signals,” IEEE Trans. Inform. Theory, Vol. IT-28, no. 1, pp. 55-67, January 1982, incorporated herein by reference) is often credited with invention of trellis-coded modulation which is a subclass of trellis codes. A trellis encoder acts on an input bit sequence to produce an output sequence of channel symbols. The codewords are therefore sequences of channel symbols of arbitrary length. The trellis encoder has a memory by virtue of a shift register being part of the encoder.
Whereas block codes usually have specific decoders that depend on the code, trellis codes are usually decoded with a sequence estimator, the most common being the well-known Viterbi algorithm (see, Forney, Jr., “The Viterbi Algorithm,” Proc. IEEE, vol. 61, pp. 268-278, March 1973, incorporated herein by reference).
As discussed above, data transmission rates continue to increase. This is especially true for today's multi-gigabit per second serial links. Conventional channel codes, while certainly useful in increasing the effective fidelity of data transmission, could stand further improvement. Accordingly, what is needed in the art is an improved trellis code. More specifically, what is needed in the art is an improved trellis code for M-PAM data transmission systems related and systems and methods for coding and decoding such trellis code.